package com.hyper_yang.algorithmRecord.backTrack;

import java.util.Arrays;
import java.util.LinkedList;

// leetcode 297 二叉树的序列化与反序列化
public class DepthFirstSearch { // depth-first search 深度优先搜索 例题
    //    序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，
//    同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
//    请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，
//    你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
//    提示: 输入输出格式与 LeetCode 目前使用的方式一致，
//    详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，
//    你也可以采用其他的方法解决这个问题。
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    // Encodes a tree to a single string.  序列化
    public String serialize(TreeNode root) {
        // 保存序列化结果
        StringBuilder res = new StringBuilder();
        res.append("[");
        dfs_serialize(res, root);
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

    // 深度优先搜索实现序列化过程
    private void dfs_serialize(StringBuilder res, TreeNode root) {
        // 判断基准情况
        if (root == null) {
            res.append("null,");
            return;
        }
        // 将当前根节点的值序列化添加到 res
        res.append(root.val + ",");
        // 处理左右子树
        dfs_serialize(res, root.left);
        dfs_serialize(res, root.right);
    }

    // Decodes your encoded data to tree.  反序列化
    public TreeNode deserialize(String data) {
        // 将数据切分，得到 “每个节点”的值
        String[] datas = data.split(",");
        LinkedList<String> datalist = new LinkedList<>(Arrays.asList(datas));

        // 删掉方括号
        String firstElement = datalist.getFirst().substring(1);
        datalist.removeFirst();
        datalist.addFirst(firstElement);

        String lastElement = datalist.getLast().substring(0, datalist.getLast().length() - 1);
        datalist.removeLast();
        datalist.addLast(lastElement);

        // 实现反序列化
        return dfs_deserialize(datalist);
    }

    private TreeNode dfs_deserialize(LinkedList<String> datalist) {
        // 基准情况 null为叶子节点
        if ("null".equals(datalist.getFirst())) {
            datalist.removeFirst();
            return null;
        }
        // 获取当前节点
        TreeNode node = new TreeNode(Integer.valueOf(datalist.getFirst()));
        datalist.removeFirst();
        node.left = dfs_deserialize(datalist);
        node.right = dfs_deserialize(datalist);
        return node;
    }


    public static void main(String[] args) {
        DepthFirstSearch dfs = new DepthFirstSearch();
        System.out.println(dfs.serialize(null));
        System.out.println(dfs.deserialize(dfs.serialize(null)));
    }
}
